/**
 * https://leetcode.cn/problems/cousins-in-binary-tree/
 */
function isCousins(root: TreeNode | null, x: number, y: number): boolean {
  const stack: TreeNode[] = [root!];
  let length = 1;
  let depth = 1;
  let oneDepth = 0;
  let oneNode: TreeNode | null = null;
  const map = new Map<number, number>();
  while (stack.length > 0) {
    const node = stack.shift()!;
    length--;
    if (node.val === x || node.val === y) {
      if (oneDepth) {
        if (depth === oneDepth && map.get(oneNode!.val) !== map.get(node.val)) {
          return true;
        } else {
          return false;
        }
      }
      oneNode = node;
      oneDepth = depth;
    }
    if (node.left !== null) {
      map.set(node.left.val, node.val);
      stack.push(node.left);
    }

    if (node.right !== null) {
      map.set(node.right.val, node.val);
      stack.push(node.right);
    }

    if (length === 0) {
      length = stack.length;
      depth++;
    }
  }

  return false;
}
